class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int sum = 0;
        // 建一个小堆
        priority_queue<int, vector<int>, greater<int>> heap;
        for(int &x : nums)
        {
            sum += x;
            heap.push(x);   // 每个数入堆
        }
        while(k--)
        {
            // 每次取堆顶的元素取反
            int x = heap.top();
            heap.pop();

            sum -= x;
            sum += x * (-1);

            // 再把取反后的结果入堆
            heap.push(x * (-1));
        }
        return sum;
    }
};